// 算法的思想是将输入数组分割成 k 个元素的块，若 n % k != 0，则最后一块元素的个数可能更少
// 开头元素为 i，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块内
// 情况 1 比较简单，建立数组 left，
// 为了处理更复杂的情况 2，我们需要数组 right 


// nums = [1,3,-1,-3,5,3,6,7], k = 3
//
// i        deq             res
// 0        [1]             []
// 1        [3]             []
// 2        [3, -1]         [3]
// 3        [3, -1, -3]     [3, 3]
// 4        [5]             [3, 3, 5]
// 5        [5, 3]          [3, 3, 5, 5]
// 6        [6]             [3, 3, 5, 5, 6]
// 7        [7]             [3, 3, 5, 5, 6, 7]

var maxSlidingWindow = function (nums, k) {
  let dequeue = [],
      res = [];
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] > dequeue[dequeue.length - 1]) dequeue.pop();
    dequeue.push(nums[i]);
    if (i >= k - 1) {
      res.push(dequeue[0]);
      if (nums[i - k + 1] === dequeue[0]) dequeue.shift();
    }
  }
  return res;
}